//给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 
//
// 示例: 
//
// 输入: n = 4, k = 2
//输出:
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
// Related Topics 回溯算法


package leetcode.d_1_99;

import java.util.LinkedList;
import java.util.List;

//Java：组合
public class P77Combinations{
    public static void main(String[] args) {
        P77Combinations solution = new P77Combinations();
        System.out.println(solution.combine(4, 2));
        // [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    }

    private int n;
    private int k;
    private List<List<Integer>> res;

    public List<List<Integer>> combine(int n, int k) {
        res = new LinkedList<>();
        if (n == 0 || k == 0){
            return res;
        }
        this.n = n;
        this.k = k;
        search(1, new LinkedList<>());
        return res;
    }

    private void search(int index, LinkedList<Integer> level) {
        if (level.size() == k){
            res.add(new LinkedList<>(level));
            return;
        }
        for (int i = index; i <= n ; i++) {
            level.add(i);
            search(i + 1, level);
            level.removeLast();
        }
    }

}